Interconnection networks are employed to forward messages between system elements in large computer and communication systems. The Internet is an interconnection network in which long messages are segmented into shorter units of information called packets which are then forwarded across the network independently through Internet routers. PCT Patent Application Serial No. PCT/US98/16762, entitled “Router with Virtual Channel Allocation,” filed Aug. 20, 1998, and published as WO99/11033, teaches an Internet router that includes an internal interconnection network referred to as a fabric. Fabrics overcome the port and bandwidth limitations commonly associated with routers that are based on common bus or crossbar switch topologies.
FIG. 1 illustrates a two dimensional torus array network which may serve as a fabric. The fabric is composed of a number of nodes 40, referred to as fabric routers, which are interconnected by fabric links 45. A fabric connects a group of external links, each coupled to a fabric router, and performs message routing and forwarding among the links. Data packets may be segmented into fixed length blocks called flow control units or flits. Flits are forwarded across the fabric using a technique called wormhole routing such that the head flit of the packet establishes a path through the fabric that is followed by the remaining flits of the packet.
FIG. 2 illustrates packet traversal over a path through a fabric. A data packet arriving on an external link is forwarded through the fabric to an external destination link by transmitting the packet over a path comprising a series of interconnected fabric routers. For example, the data packet received on node (1,4) and destined for node (5,3) may traverse a path including nodes (1,4), (2,4), (2,3), (3,3), (4,3), and (5,3). The entire path can be computed by a fabric management microprocessor at the source node, which determines the most efficient path through the fabric. The calculated path is then specified within a fabric header appended to the packet. Alternatively, a path can be computed incrementally such that each path segment is determined by a fabric management processor at each fabric hop along the path to a destination link.
FIG. 3 illustrates a typical switch element of a fabric router for forwarding data packets. A fabric router typically includes one or more switch elements 41 for forwarding data packets. The switch forwards packets received on a switch ingress port to a switch egress port. The switch radix (Δ) of a fabric corresponds to the number of fabric links 45 fanning into a switch as well as the number of fabric links 45 fanning out of the switch. For example, the switch radix is equal to 4 in FIG. 3. Fabric links fanning into a switch are connected via switch ingress ports, while fabric links fanning out of a switch are connected via switch egress ports. The remaining switch ingress ports and switch egress ports typically connect to external links (i.e., FABRIC IN and FABRIC OUT) coupled to the fabric via a line interface.
The total number of nodes in a fabric is called its size. Since the radix Δ of a switch is typically much smaller than the desired size in large fabrics, a packet will typically hop across multiple switch elements in order to traverse a fabric. The maximum number of links (i.e., hops) traversed by a packet from any source node to any destination node is called the diameter (D) of the fabric. Referring back to FIG. 2, the fabric size is 25 nodes and the diameter of the fabric is 8 hops. If the 25 nodes of FIG. 2 were connected in a torus as illustrated in FIG. 1, the diameter would be reduced to 4 hops.
When packets have random destinations, the aggregate fabric bandwidth must be greater than the product of average diameter (Davg) multiplied by the aggregate ingress access bandwidth. Since the cost of a fabric is almost directly proportional to the aggregate fabric bandwidth required, fabric topologies which reduce the average diameter for a given size result in lower fabric costs.